1. Field of the Invention
The present invention relates generally to a data compression method and apparatus, and more particularly, the present invention relates to methods and apparatus for compressing data by an adaptive multi-stage vector quantization technique.
2. Description of the Prior Art
Data compression using vector quantization ("VQ") has received great attention in the last decade because of its promising compression ratio and relatively simple structure. In its simplest implementation, VQ requires transforming data to be compressed into data vectors. For example, an image frame comprising a plurality of pixels may be sub-divided into smaller blocks of pixels, and each block may be transformed into a multi-dimensional data vector. In order to compress the data, each data vector is compared to the entries of a "codebook" containing representative "codevectors." The codevector that most closely resembles the original data vector is then selected and the codebook "address" of that codevector is then transmitted to a receiver. At the receiver, the transmitted address is used to fetch the same codevector from an identical codebook at the receiver, thus reconstructing an approximation to the original data vector. Compression is achieved because, on average, the codebook address of a codevector requires far fewer bits than transmitting the codevector itself.
Before vector quantization can be performed, a codebook of representative codevectors must be constructed. Essentially, codebooks are constructed using a sequence of "training" vectors in accordance with a codebook generation algorithm, such as the well known Linde-Buzo-Gray (LBG) algorithm. See, Y. Linde, A. Buzo and R. M. Gray, "An Algorithm for Vector Quantizer Design," IEEE Trans. Commun., vol. COM-28, pp. 84-95 (January, 1980). The performance of a vector quantizer is highly dependent upon the codebook. As one can appreciate, if the actual data vectors to be compressed by the quantizer are similar to the vectors in the "training" sequence, the reproduction quality at the receiver will be best. However, due to the large variety of possible data vectors that can arise in a given application, there may be situations where a close match for a given data vector cannot be found. In such cases, the reproduction quality will suffer.
One way to enhance the performance of a vector quantizer is to increase the size of the codebook so that the likelihood of finding a closely matching codevector for a given data vector is much greater. Unfortunately, a large codebook can require such a large memory that cost becomes prohibitive. In addition, the processing power and time needed to search a large codebook may be impractical. Several techniques have been explored for avoiding the problems that arise with large codebooks.
One very well known technique for reducing the search time with a large codebook is to employ a tree-search technique. The tree search technique is sometimes referred to as "tree-search vector quantization", "tree-search VQ" and "TSVQ." With the tree-search technique, the codebook structure resembles a tree in which codevectors reside at various nodes of the tree and the nodes are arranged in levels. Successive levels of the tree are formed by branches emanating from each node in a preceding level. Rather than comparing a data vector to every codevector in the codebook (i.e., a full-search technique), the search begins at the root node of the tree and traverses down through the levels of the tree along selected branches. Because only the codevectors along selected branches are examined, search time is greatly reduced. However, although TSVQ reduces search time, it generally does not guarantee that the best match for the data vector will be found. A detailed description of the tree search technique may be found in R. M. Gray and H. Abut, "Full Search and Tree Searched Vector Quantization of Speech Waveforms," Proc. IEEE Int. Conf. Acoust, Speech, Signal Processing, pp. 593-96 (May, 1982). A variation on the basic TSVQ technique, and a preferred method and apparatus for performing TSVQ, are disclosed in Israelsen, U.S. Pat. No. 5,172,228, entitled "Image Compression Method and Apparatus Employing Distortion Adaptive Tree search Vector Quantization," issued Dec. 15, 1992, and incorporated herein by reference.
Another solution to the problems that arise with large codebooks is to use a small, adaptive codebook which can automatically adapt to the changing characteristics of a group of data vectors. See, e.g. , M. Golberg, P. R. Boucher and S. Shlien, "Image Compression Using Adaptive Vector Quantization," IEEE Trans. Commun., vol. 34, no. 2, pp. 180-187 (February 1986). Essentially, the codebook is updated or rebuilt as the overall characteristics of the data vectors change. Of course, as the codebook in the compression apparatus changes, those changes must be transmitted to receiving locations so that the receiving locations can reproduce the original data vectors. Consequently, the overall data bandwidth is reduced. Additionally, adaptive codebooks significantly increase the complexity of vector quantizers.
Another technique for avoiding the need for large codebooks while maintaining a sufficient level of reproduction quality is know as "multi-stage vector quantization" or "MSVQ." See, e.g., B. H. Juang, and A. H. Gray, Jr., "Multiple Stage Vector Quantization for Speech Coding," Proc. IEEE ICASSP, pp. 597-600 (April, 1982). A multi-stage vector quantization encoder comprises a plurality of VQ stages arranged consecutively. Each stage has its own, relatively small codebook of representative codevectors. At the first stage, an original data vector is encoded by selecting a best match codevector from the codebook at that stage. A residual vector is then obtained by subtracting the selected codevector from the original data vector. At the next stage, the residual vector from the preceding stage is vector quantized, and so on. Each successive stage encodes the residual vector from the previous stage. As the process proceeds through each successive stage, the quantized approximation to the original data vector successively improves.
MSVQ significantly reduces memory requirements. With MSVQ, the amount of memory needed to store the codevectors of each stage is proportional to the number of stages, whereas, in a conventional TSVQ encoder using a single large codebook, the amount of memory needed is exponentially proportional to the codebook address size. For example, a multi-stage vector quantization encoder with six (6) stages that each employ a codebook of 2.sup.4 codevectors requires a storage capacity of 96 codevectors (6 stages.times.2.sup.4 codevectors/stage). With a tree-search vector quantizer, however, a single codebook containing approximately 2.sup.24 (.apprxeq.16 million) codevectors is required in order to achieve a similar degree of encoding accuracy. As can be seen from the foregoing illustration, the MSVQ technique is extremely advantageous from a memory standpoint.
Although MSVQ avoids many of the problems that arise with excessively large codebooks, performance rapidly diminishes as the number of stages increases. Also, it is not always necessary to proceed through every stage of a multi-stage vector quantization encoder. For example, a data vector may be sufficiently encoded after only a few stages, and further encoding at subsequent stages may not create a visually perceptible increase in reproduction quality at a decoder. An article by Y. Ho and A. Gersho, entitled "Variable-Rate Multi-stage Vector Quantization for Image Coding," presented at the 1989 International Conference on Acoustics, Speech, and Signal Processing (ICASSP), describes a multi-stage encoder in which thresholds are employed to selectively encode the residual image data at the last two stages of a five stage encoder. According to Ho and Gersho, when the fourth stage of the encoder is reached, the residual vector at that stage is vector quantized only if the squared sum of residual errors remaining at that stage exceeds a first threshold value. If the threshold is satisfied, then no encoding occurs at that stage, and the residual is simply passed to the fifth or last stage. At the last stage, the error remaining is compared to a second, smaller threshold value. Again, if the threshold value is satisfied, the residual vector is not encoded at the last stage. Encoding at the last stage occurs only if the threshold value is exceeded. According to the technique of Ho and Gersho, therefore, the encoding process always proceeds through to the last stage of the encoder, but encoding may not take place at either one of the last two stages. While the technique described by Ho and Gersho may result in some increase in encoding efficiency, the method is disadvantageous for at least four reasons. First, vector quantization is always performed at the first three stages, even though the increased encoding accuracy provided at each successive stage may not be visibly perceptible at a decoder. Second, even when the threshold value is satisfied in the fourth stage, encoding may still be performed at the last stage. Thus, some form of processing occurs at every stage of the encoder despite the use of threshold values in the fourth and fifth stages. Third, although Ho and Gersho mention that different threshold values can be used to alter the trade-off between bit-rate and encoding accuracy, the threshold values for a given application are pre-determined and remain fixed during vector processing. Finally, although Ho and Gersho recognize that their multi-stage vector quantization encoder will produce data at a variable rate, they fail to address the need for maintaining a fixed rate data stream over a communications channel. Variable rate transmission is often impractical because most transmission mediums are susceptible to noise. As the foregoing illustrates, therefore, a more advantageous solution to the problems inherent in most prior art multi-stage vector quantization encoders is needed. The present invention satisfies this need.